package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //和为 K 的子数组
        class Solution {
            public int subarraySum(int[] nums, int k) {
                // 哈希表：存前缀和 -> 出现次数
                Map<Integer, Integer> hash = new HashMap<>();
                hash.put(0, 1); // 模拟前缀和数组 sum[0] = 0

                int sum = 0, ans = 0;
                for (int x : nums) {
                    sum += x; // 累加前缀和
                    // 如果 sum - k 出现过，说明存在子数组和为 k
                    ans += hash.getOrDefault(sum - k, 0);
                    // 更新哈希表，记录当前前缀和出现次数
                    hash.put(sum, hash.getOrDefault(sum, 0) + 1);
                }
                return ans;
            }
        }


        //和可被 K 整除的子数组
        class Solution2 {
            public int subarraysDivByK(int[] nums, int k) {
                Map<Integer, Integer> hash = new HashMap<>();
                hash.put(0, 1); // 前缀和为0的余数，出现1次
                int sum = 0, ret = 0;

                for (int x : nums) {
                    sum += x;
                    int r = (sum % k + k) % k; // 修正负数余数
                    ret += hash.getOrDefault(r, 0); // 找到已有多少相同余数
                    hash.put(r, hash.getOrDefault(r, 0) + 1); // 更新出现次数
                }

                return ret;
            }
        }

    }
}